Zkouška Mareš 9. 6. 2023
Násobení čísel lépe než kvadraticky
Bellman-Fordův algoritmus s důkazem složitosti
Je dán slovník. Sestrojte co nejdelší slovní žebřík. To je posloupnost slov ze slovníku taková, že (i+1)-ní slovo získáme z i-tého smazáním jednoho písmene. Například pro anglický slovník AGID-4 vychází žebřík glassiness, glassines, glassine, glassie, lassie, lassi, lass, ass, as, a.
Je dáno číslo K. Na vstupu přichází celá čísla, po příchodu dalšího čísla vždy vypíšeme minimum z posledních K čísel.
Mé řešení.
První úlohu chtěl dost detailně, tedy chtěl vidět všechny části a návaznosti, (např: Proč využívám 3 rekurze a co mě k tomu vedlo.). 2) Základní popis algoritmu a hlavně důkaz algoritmu + odvození složitosti. Myslím si, že základ úspěchu u Mareše je znát teorii. Zkouška probíhá úplně stejně, jako na diskrétce.
úlohu jsem vyřešil na pomalý čas a tudíž nebyla plně schválena. Mé řešení porovnalo každá slova ve slovníku s každým, tento proces je lineární vůči maximální délce slova a kvadratický, protože každé slovo s každým, takže O(l*n^2) pro l jako max délka slova, ale lze to kontrolovat jen z jedné strany a tím to ulehčit lehce, a následně z toho vytvořil DAG. DAG určoval jaké slova jdou s čím zžebříkovat a potom stačilo najít nejdelší cestu v DAGu.
Toto řešení bylo schváleno. Vložím Ktici čísel do haldy a do queue. Min halda nám v kořeni vždy dá minimum a když přidáváme a odebereme prvek, tak stačí z queue vytáhnout další prvek co má uloženou pozici čísla v haldě a z té haldy ho smazat.